from timeit import Timer
from BaseConvert import *

import sys
import math


def Problem():
    """The decimal number, 585 = 1001001001_(2) (binary), 
    is palindromic in both bases.

    Find the sum of all numbers, less than one million, 
    which are palindromic in base 10 and base 2.

    (Please note that the palindromic number, in either base, 
    may not include leading zeros.)
    """


    #Method 1 - brute force
    is_pal = lambda x: str(x) == str(x)[::-1] and str(bin(x)) == str(bin(x))[::-1] 
    #numbers = [n for n in xrange(1, 1000000) if is_pal(n)]
    
    #ans = sum(numbers)


    #Method 2 - building from binary number
    
    """Since the leading number much be 1, then last number
    will also be 1, thus odd numbers. If palindrom string is
    even then half the numbers repeat in reverse direction. If
    palindrom is odd, then half minus 1 numbers repeat in reverse
    direction."""
    
    
    make_pals = lambda n: [str(n) + str(n)[::-1], str(n) + str(n)[::-1][1:]]   
    limit = int('1'*(len(bin(10**6))/2), 2)
    num1 = map(make_pals, xrange(1, limit))
        

    num = []
    map(lambda x: num.extend(x), num1)
    num = filter(is_pal, num)
    num = map(lambda x: int(x), num)
    #ans = reduce(lambda x, y: int(x) + int(y), num)
    ans = sum(num)

    
    
    print "Answer for Problem 36 = %d" % (ans,)
    

    
if __name__ == "__main__":
    t = Timer(setup='from __main__ import Problem', stmt='Problem()').timeit(1)
    print "Execution time = %0.3f seconds" %(t,)